//
//  844. 比较含退格的字符串.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/15.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution844 {
    func backspaceCompare(_ s: String, _ t: String) -> Bool {
        let sArray = Array(s)
        let tArray = Array(t)
        
        var p1 = s.count - 1
        var p2 = t.count - 1
        
        while p1 >= 0 || p2 >= 0 {
            // 左边的数组
            var skip1 = 0
            while p1 >= 0 {
                if sArray[p1] == "#" {
                    skip1 += 1
                    p1 -= 1
                    continue
                }
                if skip1 != 0 {
                    p1 -= 1
                    skip1 -= 1
                } else{
                    // 字符固定了
                    break
                }
            }
            // 右边的数组
            var skip2 = 0
            while p2 >= 0 {
                if tArray[p2] == "#" {
                    skip2 += 1
                    p2 -= 1
                    continue
                }
                if skip2 != 0 {
                    p2 -= 1
                    skip2 -= 1
                } else{
                    // 字符固定了
                    break
                }
            }
            // 如果在中途相等
            if p1 >= 0 && p2 >= 0 {
                if sArray[p1] != tArray[p2] {
                    return false
                }
            } else {
                // 如果不是在中途相等，有一个已经结束，另个没有结束
                if p1 >= 0 || p2 >= 0 {
                    return false
                }
            }
            p1 -= 1
            p2 -= 1
        }
        return true
    }
    
    static func test() {
        let solution = Solution844()
        let s = "nzp#o#g"
        let t = "b#nzp#o#g"
        let result = solution.backspaceCompare(s, t)
        print(result)
    }
}
